﻿// 0827train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <deque>
#include <map>
#include <set>

using namespace std;

/*
 "ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列

 示例 1
输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是 "ace" ，它的长度为 3
 */
class Solution01 {
public:
    int longestCommonSubsequence(string text1, string text2) {
        row_size = text1.size() + 1;
        col_size = text2.size() + 1;

        vector<vector<int>>dynamic_grid(row_size, vector<int>(col_size));
        //dp[r][c] text1的前r，text2前c 公共子序列
        //text1[r-1]==text2[c-1]该字符进公共子序，dp[r][c]=dp[r-1][c-1]+1
        //不相等，3种情况取max
        //r在，c不在 dp[r][c]=dp[r][c-1]
    	//r不在，c在 dp[r][c]=dp[r-1][c]
        //r,c都不在（不用写，一定小于前2种情况）
        dynamic_grid[0][0] = 0; //dp[0][c]=0 dp[r][0]=0

        for (int r=1; r<row_size; r++)
        {
            for (int c=1; c<col_size; c++)
            {
                if (text1[r-1]==text2[c-1])
                {
                    //text1[r - 1] == text2[c - 1]该字符进公共子序，dp[r][c] = dp[r - 1][c - 1] + 1
                    dynamic_grid[r][c] = dynamic_grid[r - 1][c - 1] + 1;
                }
                else
                {
                    //r在，c不在 dp[r][c]=dp[r][c-1]
					//r不在，c在 dp[r][c]=dp[r-1][c]
                    dynamic_grid[r][c] = max(dynamic_grid[r][c - 1], dynamic_grid[r - 1][c]);

                }

            }
        }
        return dynamic_grid[text1.size()][text2.size()];
    }
private:
    int row_size = 0, col_size = 0;
};


/*
 给两个整数数组 nums1 和 nums2 ，返回两个数组中公共的 、长度最长的子数组的长度 

示例 1
输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3,2,1]
 */
class Solution02
{
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        row_size = nums1.size() + 1;
        col_size = nums2.size() + 1;

        vector<vector<int>>dynamic_grid(row_size, vector<int>(col_size));

        int max_length = 0;
        for (int r=1; r<row_size; r++)
        {
            for (int c=1; c<col_size; c++)
            {
                if (nums1[r-1]==nums2[c-1])
                {
                    dynamic_grid[r][c] = dynamic_grid[r - 1][c - 1] + 1;
                }
                max_length = max(max_length, dynamic_grid[r][c]);
            }
        }
        return max_length;
    }
private:
    int row_size = 0, col_size = 0;
};

/*
 两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警
 示例 1
输入：nums = [1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)
     偷窃到的最高金额 = 1 + 3 = 4 
 */
class Solution03
{
public:
    int rob(vector<int>& nums) 
    {
        if (nums.empty()) return 0;
        if (nums.size() == 1) return nums[0];

        //dp[i]走到前i个房的最高金额
        //1打劫i dp[i]=dp[i-1]
        //2不打劫i dp[i]=dp[i-2]+nums[i-1]
        int dp_size = nums.size()+1;
        vector<int>dynamic_vec(dp_size);

        dynamic_vec[0] = 0; //前0个等于0
        dynamic_vec[1] = nums[0]; //前1个等于nums[0]

        for (int i=2; i<dp_size; i++)
        {
            //打劫i，不打劫i
            dynamic_vec[i] = max(dynamic_vec[i - 1], dynamic_vec[i - 2] + nums[i - 1]);
        }

        return dynamic_vec[nums.size()];
    }
private:
};

/*
 示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4
 */

class Solution04
{
public:
    int lengthOfLIS(vector<int>& nums)
	{
        //初始化，1，即使没有一个数小于i，子序列长度1
        int dp_size = nums.size();

        vector<int>dynamic_vec(dp_size, 1);

        //转移方程
        //取最值，因为不止一个小于i
        //dp[i] = max(dp[i], dp[prev]+1)
        dynamic_vec[0] = 1; //0位置只有1个数，肯定为1

        for (int i=1; i<dp_size; i++)
        {
	        for (int prev=0; prev<i; prev++)
	        {
                if (nums[i]>nums[prev])
                {
                    dynamic_vec[i] = max(dynamic_vec[i], dynamic_vec[prev] + 1);
                }
	        }
        }

        int result = 0;
        for (auto&length:dynamic_vec)
        {
            result = max(result, length);
        }
        return result;
    }
};


/*
 
 */
class Solution05 {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        row_size = nums1.size() + 1;
        col_size = nums2.size() + 1;

        vector<vector<int>>dynamic_grid(row_size, vector<int>(col_size));

        //if(nums1[r-1]==nums2[c-1]) dp[r][c]=dp[r-1][c-1]+1

        dynamic_grid[0][0] = 0; //dp[0][c]=0 dp[r][0]=0

        
        for (int r=1; r<row_size; r++)
        {
            for (int c=1; c<col_size; c++)
            {
                if (nums1[r-1]==nums2[c-1])
                {
                    dynamic_grid[r][c] = dynamic_grid[r - 1][c - 1] + 1;
                }
                else
                {
                    dynamic_grid[r][c] = max(dynamic_grid[r][c - 1], dynamic_grid[r - 1][c]);
                }
            }
        }
        return dynamic_grid[nums1.size()][nums2.size()];
    }
private:
    int row_size = 0, col_size = 0;
};

int main()
{
	{
        //nums1 = [1,4,2], nums2 = [1,2,4]
        vector<int>nums1 = { 2,5,1,2,5 }, nums2 = { 10,5,2,1,5,2 };
        Solution05 solu;
        cout << solu.maxUncrossedLines(nums1, nums2);

        return 0;
	}
	{
        //nums = [10,9,2,5,3,7,101,18]
        vector<int>nums = { 10,9,2,5,3,7,101,18 };

        Solution04 solu;
        cout << solu.lengthOfLIS(nums);

        return 0;
	}
	{
        //nums = [1,2,3,1]
        vector<int>nums = { 1,2,3,1 };
        Solution03 solu;
        cout << solu.rob(nums);

        return 0;
	}
	{
        //nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7] 3
        vector<int>nums1 = { 1,2,3,2,1 }, nums2 = { 3,2,1,4,7 };
        Solution02 solu;
        cout << solu.findLength(nums1, nums2);

        return 0;
	}
    //text1 = "abcde", text2 = "ace" 3
    string text1 = "abcde", text2 = "ace";
    Solution01 solu;
    cout << solu.longestCommonSubsequence(text1, text2);

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
